<html>
 <head>
  <meta charset="UTF-8">
 </head>
 <body>
  <h1 data-lake-id="fyZER" id="fyZER"><span data-lake-id="uba51d9fd" id="uba51d9fd">典型回答</span></h1>
  <p data-lake-id="ub61b0c12" id="ub61b0c12"><span data-lake-id="u38f5ec92" id="u38f5ec92">​</span><br></p>
  <p data-lake-id="u2a0088bc" id="u2a0088bc"><span data-lake-id="u433cf96b" id="u433cf96b">时间轮算法（Time Wheel Algorithm）是一种用于处理定时任务和调度的常见算法。</span></p>
  <p data-lake-id="u0aadb6a2" id="u0aadb6a2"><span data-lake-id="u36d095d1" id="u36d095d1">​</span><br></p>
  <p data-lake-id="u312e8122" id="u312e8122"><span data-lake-id="u97ab8d86" id="u97ab8d86">时间轮算法主要需要定义一个时间轮盘，在一个时间轮盘中划分出多个槽位，每个槽位表示一个时间段，这个段可以是秒级、分钟级、小时级等等。如以下就是把一个时间轮分为了60个时间槽，每一个槽代表一秒钟。</span></p>
  <p data-lake-id="ued3a8dc9" id="ued3a8dc9"><span data-lake-id="u22876ae4" id="u22876ae4">​</span><br></p>
  <p data-lake-id="u825f623f" id="u825f623f"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1697873301595-c5043edb-53b9-4092-839b-dc2f0ddc208f.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_18%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u527363c6" id="u527363c6"><span data-lake-id="u5409591b" id="u5409591b">​</span><br></p>
  <p data-lake-id="u096ba60d" id="u096ba60d"><span data-lake-id="u272e7b7b" id="u272e7b7b">然后当我们有定时任务需要执行的时候，就把他们挂在到这些槽位中，这个任务将要在哪个槽位中执行，就把他挂在到哪个槽位的链表上。</span></p>
  <p data-lake-id="u980f6f26" id="u980f6f26"><br></p>
  <p data-lake-id="u6a8456a5" id="u6a8456a5"><span data-lake-id="uf95ffb55" id="uf95ffb55">比如当前如果是0秒，那么要3秒后执行，那就挂在槽位为3的那个位置上。</span></p>
  <p data-lake-id="uba5bcb95" id="uba5bcb95"><span data-lake-id="u905653cc" id="u905653cc">​</span><br></p>
  <p data-lake-id="ucf9ffcf1" id="ucf9ffcf1"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1697873440333-06e5af62-1795-4891-9f9b-85e3aba1ca72.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_29%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u7538398b" id="u7538398b"><span data-lake-id="ub7d387a9" id="ub7d387a9">​</span><br></p>
  <p data-lake-id="uc547f7c0" id="uc547f7c0"><span data-lake-id="u2a623a04" id="u2a623a04">而随着时间的推移，轮盘不断旋转，任务会被定期触发。</span></p>
  <p data-lake-id="u127cbd6b" id="u127cbd6b"><span data-lake-id="u7861207c" id="u7861207c">​</span><br></p>
  <p data-lake-id="uc6d675ae" id="uc6d675ae"><span data-lake-id="uda112731" id="uda112731">因为这个时间轮是60个槽位，那么他就会在一分钟完整的转完一圈，那么就有一个指针，每一秒钟在槽位中进行一次移动。这个操作是有一个单独的线程来做的，他的工作就是每一秒钟改变一次current指针。</span></p>
  <p data-lake-id="ubc41a03f" id="ubc41a03f"><span data-lake-id="u7ab6ebb2" id="u7ab6ebb2">​</span><br></p>
  <p data-lake-id="u7f6a35cc" id="u7f6a35cc"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1697873554531-74fc4e6e-b3de-4791-8cae-4caa67ed4ad9.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_30%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="ufface62d" id="ufface62d"><span data-lake-id="ud87d733c" id="ud87d733c">​</span><br></p>
  <p data-lake-id="u6ef3f33a" id="u6ef3f33a"><span data-lake-id="u9720aa34" id="u9720aa34">然后还有一个线程池，在指针轮转到某个槽位上的时候，在线程池中执行链表中需要执行的任务。</span></p>
  <p data-lake-id="u40697186" id="u40697186"><span data-lake-id="u5323a572" id="u5323a572">​</span><br></p>
  <p data-lake-id="uc38ab5e3" id="uc38ab5e3"><span data-lake-id="ubfee01d5" id="ubfee01d5">以上就是一个简单的时间轮算法，但是这个时间轮存在一个问题，那就是我们把它分了60个槽，那么就意味着我们的定时任务最多只支持60s以内的。</span></p>
  <p data-lake-id="ub7eb5201" id="ub7eb5201"><span data-lake-id="uc83897ed" id="uc83897ed">​</span><br></p>
  <p data-lake-id="u4dab7123" id="u4dab7123"><strong><span data-lake-id="u61f56466" id="u61f56466">那么，怎么解决这个问题呢？</span></strong></p>
  <p data-lake-id="u1c529e9f" id="u1c529e9f"><span data-lake-id="ud640962a" id="ud640962a">​</span><br></p>
  <p data-lake-id="u6d9fbf04" id="u6d9fbf04"><span data-lake-id="ue97c850a" id="ue97c850a">首先能想到的最简单的方式就是加槽位，比如我要支持5分钟的延迟任务，那么就可以把槽位设置为300个。</span></p>
  <p data-lake-id="u53b885f2" id="u53b885f2"><span data-lake-id="u22042f35" id="u22042f35">​</span><br></p>
  <p data-lake-id="ue99441e4" id="ue99441e4"><span data-lake-id="u44d77da4" id="u44d77da4">还有就是也可以调整时间轮槽位移动的延迟，比如把1秒钟移动一次，改为1分钟移动一次，那么就可以支撑60分钟的延迟任务了。</span></p>
  <p data-lake-id="ud01a4ab0" id="ud01a4ab0"><span data-lake-id="ufeaa94cf" id="ufeaa94cf">​</span><br></p>
  <p data-lake-id="uca83ca3a" id="uca83ca3a"><span data-lake-id="u69c8ceef" id="u69c8ceef">但是这两个办法都不够灵活，而且是有瓶颈的。于是有一种新的办法。</span></p>
  <p data-lake-id="u09a5a845" id="u09a5a845"><span data-lake-id="ua1e00e9f" id="ua1e00e9f">​</span><br></p>
  <h3 data-lake-id="qMzkD" id="qMzkD"><span data-lake-id="uf86bf8e5" id="uf86bf8e5">round</span></h3>
  <p data-lake-id="u16be9712" id="u16be9712"><span data-lake-id="ue8b5a1a3" id="ue8b5a1a3">​</span><br></p>
  <p data-lake-id="uc13c1c37" id="uc13c1c37"><span data-lake-id="u50495ad9" id="u50495ad9">在时间轮中增加一个round的标识，标识运行的圈数，比如说上面的60s的时间轮，如果我要200s之后运行，那么我在设置这个任务的时候，就把他的round设置为 200/60 = 3 ，然后再把它放到 200%60 = 20的这个槽位上。</span></p>
  <p data-lake-id="u6975bdfb" id="u6975bdfb"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1697874971503-d956287f-15a0-4338-aa32-cc0b58f80c37.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_23%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u6272020a" id="u6272020a"><span data-lake-id="ube2fe376" id="ube2fe376">​</span><br></p>
  <p data-lake-id="ue143ea68" id="ue143ea68"><span data-lake-id="u99f806dc" id="u99f806dc">有了这个round之后，每一次current移动到某个槽位时，检查任务的round是不是为0，如果不为0，则减一。</span></p>
  <p data-lake-id="u8a77ab16" id="u8a77ab16"><span data-lake-id="ue04b50a4" id="ue04b50a4">​</span><br></p>
  <p data-lake-id="uc0c6c15a" id="uc0c6c15a"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1697874978637-e06248d5-af75-4813-8619-fc10da663e57.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_44%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u14c2dec7" id="u14c2dec7"><span data-lake-id="u827db9c4" id="u827db9c4">​</span><br></p>
  <p data-lake-id="u1060ce87" id="u1060ce87"><span data-lake-id="u4ebcdeb3" id="u4ebcdeb3">这样时间轮转到第三圈时，round的值会变成0，再第四圈运行到current=20的时候，发现round=0了，那么就可以执行这个任务了。</span></p>
  <p data-lake-id="u372ac6f9" id="u372ac6f9"><span data-lake-id="ua58b8ddb" id="ua58b8ddb">​</span><br></p>
  <p data-lake-id="u11ecd962" id="u11ecd962"><span data-lake-id="uab729b98" id="uab729b98">这样就解决了我们前面说的问题了。</span></p>
  <p data-lake-id="u4a326840" id="u4a326840"><span data-lake-id="ub1e8a9e0" id="ub1e8a9e0">​</span><br></p>
  <p data-lake-id="uffb70cb4" id="uffb70cb4"><span data-lake-id="uae744ff0" id="uae744ff0">但是这个方案还存在一个问题，那就是这个round的检查过程，需要把所有任务都遍历一遍，效率还是没那么高。</span></p>
  <p data-lake-id="u50ce76c2" id="u50ce76c2"><span data-lake-id="u971cc9e4" id="u971cc9e4">​</span><br></p>
  <h3 data-lake-id="AbGY0" id="AbGY0"><span data-lake-id="ue5bf51c7" id="ue5bf51c7">分层时间轮</span></h3>
  <p data-lake-id="ub677a6c9" id="ub677a6c9"><br></p>
  <p data-lake-id="u3f718e67" id="u3f718e67"><span data-lake-id="u7cbdb266" id="u7cbdb266">为了解决遍历所有任务的问题，我们可以引入分层时间轮。我们在刚刚的秒级时间轮的基础上，在定义一个分钟级时间轮</span></p>
  <p data-lake-id="ubaa9b93d" id="ubaa9b93d"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1697875385784-e89694fa-ff8d-4780-a6f8-5362db202b00.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_36%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u35cb2fbc" id="u35cb2fbc"><span data-lake-id="u01ec7c53" id="u01ec7c53">​</span><br></p>
  <p data-lake-id="uc93708a9" id="uc93708a9"><span data-lake-id="ue73cdca9" id="ue73cdca9">也就是说我们对于200s以后执行这个任务，我们先把他放到分钟级时间轮上，这个时间轮的槽位每一分钟移动一次，当移动时候，发现某个槽位上有这一分钟内需要执行的任务时。</span></p>
  <p data-lake-id="uafaa883f" id="uafaa883f"><span data-lake-id="u4988c551" id="u4988c551">​</span><br></p>
  <p data-lake-id="uadea4dd9" id="uadea4dd9"><span data-lake-id="u0eecc0b5" id="u0eecc0b5">把这个任务取出来，放到秒级时间轮中。这样在第3分20秒的时候，就可以运行这个任务了。</span></p>
  <p data-lake-id="u35969063" id="u35969063"><span data-lake-id="u0fef100a" id="u0fef100a">​</span><br></p>
  <p data-lake-id="ue94adf9d" id="ue94adf9d"><span data-lake-id="u289d73ec" id="u289d73ec">这就是分层时间轮。在分层时间轮包括多个级别的时间轮，每个级别的时间轮都有不同的粒度和周期。</span></p>
  <p data-lake-id="u2bc30dfb" id="u2bc30dfb"><span data-lake-id="u826a3c28" id="u826a3c28">​</span><br></p>
  <p data-lake-id="u159a176c" id="u159a176c"><span data-lake-id="u5b75bae3" id="u5b75bae3">通常，粒度较细的时间轮拥有更短的周期，而粒度较粗的时间轮拥有更长的周期。例如，分层时间轮可以包括毫秒级、秒级、分钟级等不同粒度的时间轮。</span></p>
  <p data-lake-id="ucf2b8878" id="ucf2b8878"><span data-lake-id="ua29fe3d5" id="ua29fe3d5">​</span><br></p>
  <p data-lake-id="ue39e3dec" id="ue39e3dec"><span data-lake-id="u4244bd63" id="u4244bd63">当一个任务需要被调度时，它被分配到适当级别的时间轮中，每个级别的时间轮都独立地旋转。当一个时间轮的指针到达某个位置时，它将触发执行该级别时间轮中的任务。如果某个任务在较粗的时间轮中已经到期，它将被升级到下一级时间轮。</span></p>
  <p data-lake-id="u31ca5ff9" id="u31ca5ff9"><span data-lake-id="u73a1d204" id="u73a1d204">​</span><br></p>
  <p data-lake-id="u2872e997" id="u2872e997"><span data-lake-id="u6be1652c" id="u6be1652c">当任务升级到下一级时间轮时，任务的调度粒度变得更细。这意味着任务将在更短的时间内被触发，从而更精确地满足其调度要求。</span></p>
  <p data-lake-id="ucce08a45" id="ucce08a45"><span data-lake-id="u66f161d5" id="u66f161d5">​</span><br></p>
  <p data-lake-id="ufbe2e395" id="ufbe2e395"><span data-lake-id="u81c7be9e" id="u81c7be9e">​</span><br></p>
  <h1 data-lake-id="H2PIv" id="H2PIv"><span data-lake-id="u33c25f69" id="u33c25f69">扩展知识</span></h1>
  <p data-lake-id="ud45087b6" id="ud45087b6"><br></p>
  <h2 data-lake-id="SLhHb" id="SLhHb"><span data-lake-id="u74cc1f34" id="u74cc1f34">典型应用</span></h2>
  <p data-lake-id="u802d2c76" id="u802d2c76"><br></p>
  <p data-lake-id="ud53d3b18" id="ud53d3b18"><span data-lake-id="uaf779f74" id="uaf779f74">时间轮算法在各种框架和库中都有广泛的应用。以下是一些应用时间轮算法的常见框架和库：</span></p>
  <p data-lake-id="u8f6acc24" id="u8f6acc24"><span data-lake-id="u2181739e" id="u2181739e">​</span><br></p>
  <ol list="u4253c8b5">
   <li fid="uc249f089" data-lake-id="u825b54b3" id="u825b54b3"><span data-lake-id="u46dfd375" id="u46dfd375">Netty</span><span data-lake-id="ud3091eb0" id="ud3091eb0">：Netty 是一款高性能的网络通信框架，它使用时间轮算法来处理定时任务和超时检测。时间轮用于管理通道的超时和重连机制。</span></li>
   <li fid="uc249f089" data-lake-id="u8557a57d" id="u8557a57d"><span data-lake-id="ue5772859" id="ue5772859">Akka：Akka 是一个并发编程框架，它包括一个调度器，该调度器使用时间轮算法来管理和触发并发任务。这使得 Akka 能够支持高并发和复杂的任务调度需求。</span></li>
   <li fid="uc249f089" data-lake-id="u2c8c2afc" id="u2c8c2afc"><span data-lake-id="u6054cdce" id="u6054cdce">Kafka</span><span data-lake-id="uc86ef015" id="uc86ef015">：Apache Kafka 是一个分布式消息队列系统，它使用时间轮算法来管理消息的过期和删除。时间轮用于清理过期消息，以释放存储空间。</span></li>
   <li fid="uc249f089" data-lake-id="u20ccbbd6" id="u20ccbbd6"><span data-lake-id="u96cb80df" id="u96cb80df">Hystrix：Hystrix 是 Netflix 开发的容错和延迟容忍库，它使用时间轮来管理命令执行和熔断状态的转换。</span></li>
   <li fid="uc249f089" data-lake-id="ub4ae4e9f" id="ub4ae4e9f"><span data-lake-id="ua5887cca" id="ua5887cca">Disruptor</span><span data-lake-id="ube7c78d0" id="ube7c78d0">：Disruptor 是一个高性能并发框架，它使用时间轮算法来管理任务的并发执行，以提高处理大量事件的性能。</span></li>
   <li fid="uc249f089" data-lake-id="ub6a251c5" id="ub6a251c5"><span data-lake-id="u0645c067" id="u0645c067">xxl-job：在以前的版本的xxl-job中，使用quartz做定时任务调度，但是在7.28版本中去除了quartz，改用了时间轮算法。<br></span><span data-lake-id="u3f3c69be" id="u3f3c69be"> </span></li>
  </ol>
  <p data-lake-id="u115dc5ab" id="u115dc5ab"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1697875873292-a3511d75-8a26-414b-99e5-5821485f9a59.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_37%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
 </body>
</html>